| | Category | CS | P07 | Finding Efficient Shellsort Sequences Using Genetic Algorithms |
| | Abstract | Shellsort, discovered by D. L. Shell in 1959, is a sorting algorithm whose |
| | performance depends on the increment sequence chosen. Even though |
| | many attempts have been made to find an optimal sequence to allow |
| | Shellsort to reach the lower bound of O(n log(n)) for comparison sorts, no |
| | such sequence has been discovered. This paper presents a method to |
| | find efficient increment sequences through the use of genetic algorithms |
| | and compares the performance of Shellsort with these sequences to |
| | merge sort and Shellsort with other known remarkable sequences. It is |
| | concluded that the sequences found through genetic algorithms perform |
| | exceptionally compared to merge sort and Shellsort with other sequences |
| | even though they do not reach O(n log(n)) performance. |
| | Bibliography | Michael Main. Mergesort.java, June 1998. |
| | |
| | V. Pratt. Shellsort and sorting networks. PhD thesis, Stanford University, |
| | 1971. |
| | |
| | Mark Allen Weiss. Lower bounds for shellsort. PhD thesis, Princeton |
| | University, 1987. |